/*
https://leetcode-cn.com/problems/design-add-and-search-words-data-structure/solution/tian-jia-yu-sou-suo-dan-ci-shu-ju-jie-go-n4ud/
 */
public class Solution211 {

    Trie trie;

    public Solution211() {
        trie=new Trie();
    }

    public void addWord(String word) {
        trie.insert(word);
    }

    public boolean search(String word) {
        return dfs(word,0,trie);
    }

    public boolean dfs(String s,int k,Trie trie){
        if (k==s.length()){
            return trie.isEnd;
        }
        char ch=s.charAt(k);
        if (ch!='.'){
            Trie child=trie.tries[ch-'a'];
            if (child!=null && dfs(s,k+1,child)==true){
                return true;
            }
        }else {
            for (int i = 0; i < 26; i++) {
                Trie child=trie.tries[i];
                if (child!=null && dfs(s,k+1,child)==true){
                    return true;
                }
            }
        }
        return false;
    }

    public static class Trie{
        boolean isEnd=false;
        Trie[] tries=new Trie[26];

        void insert(String s){
            Trie node=this;
            for (int i=0;i<s.length();i++){
                char c=s.charAt(i);
                int index=c-'a';
                if (node.tries[index]==null){
                    node.tries[index]=new Trie();
                }
                node=node.tries[index];
            }
            node.isEnd=true;
        }
    }

    public static void main(String[] args) {
        Solution211 solution211=new Solution211();
        solution211.addWord("bad");
        solution211.addWord("dad");
        solution211.addWord("mad");
        System.out.println(solution211.search("pad"));
        System.out.println(solution211.search("bad"));
        System.out.println(solution211.search(".ad"));
        System.out.println(solution211.search("b.."));
    }
}
